The final steps of Dijkstra's algorithm involve relaxing the last edges and handling stale entries in the Priority Queue.
- Loop 3: Node C (cost 3) is popped. We relax edge C → D, finding a new path cost of $3 + 1 = 4$.
- Since $4 < d[D]=6$, we update $d[D]=4$ and push the new entry (4, D) to the PQ.
- Loop 4: The stale entry (4, C) is popped. Since C is already finalized (visited), this entry is ignored, demonstrating how the PQ handles updates.
- Loop 5: The optimal entry (4, D) is popped. Node D is finalized with a shortest distance of 4.
- Loop 6: The final stale entry (6, D) is popped and ignored because D is already visited.
- The Priority Queue is now empty, and the algorithm terminates, having found the shortest path to all reachable nodes.
- The final shortest path to D is A → B → C → D with a total cost of 4.
| Node | Final $d[v]$ (Distance) | Final $prev[v]$ (Predecessor) |
|---|---|---|
| A | 0 | None |
| B | 1 | A |
| C | 3 | B |
| D | 4 | C |